/**
 * @program: LeetCode
 * @description: LeetCode :
 * @author: WXY
 * @create: 2022-12-24 18:54
 * @Version 1.0
 **/

public class Num234_isPalindrome {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode n1 = head;
        ListNode n2 = head;
        while (n2.next != null && n2.next.next != null) {
            n1 = n1.next; //n1 来到了中点
            n2 = n2.next.next; // n2 到了结尾或者是倒数第二个节点
        }
        ListNode n3 = null;
        n2 = n1.next;
        n1.next = n3;
        while (n2 != null) {
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }
        //此时n1来到了最后一个节点，n2 n3都是null
        n3 = n1;
        n2 = head;
        //比较
        boolean ans = true;
        while (n1 != null && n2 != null) {
            if (n1.val != n2.val) {
                return false;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        //将后半部分反转
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return true;
    }

}
